COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SS(Syntax-directed Processes,syntax-directed,P286:)
C00016 00003	.REQUIRE "NOTES.PDQ" SOURCE_FILE
C00017 ENDMK
C⊗;
.SS(Syntax-directed Processes,syntax-directed,P286:)
.SELECT 1
.TURN ON "←";
.FP
This project is only an introduction
to the very important area of %2syntax-directed processes%*.
As the name implies, there is a close relationship between
the syntax specification of an object, and the computational
rules which we wish to apply.
Syntax-directed techniques are used extensively in compiler construction,
relating the syntax equations to the code generation.
We shall begin by applying syntax-directed techniques to evaluation.

We know that  there are alternatives to the call-by-value
evaluation scheme; and we know there are alternatives to 
the prefix notation which we  chose to represent function application.

For example, in grade school we all learned infix notation and
its implied precedence relations, say for + and *. Simply because
infix notation is the first representation we see doesn't mean that
it is the most convenient for evaluation either by us or by machine.

Let's take as example the expression:  2+3*5.
The grade school precedence relations say that * takes ⊗→precedence↔←
over +.  That is, the expression represents 
2+(3*5) rather than (2+3)*5.
When we  write the expression in prefix notation:
+[2;*[3;5]],  the precedence of operations
is made explicit. Similarly, postfix notation (where the operators
follow rather than precede the operands) is easy:
[2;[3;5]*]+.

Some notational schemes
lend themselves to mechanical evaluation better than others.
There is a certain amount of implied intelligence required in the usual
infix scheme.  We have already  seen one very mechanical method for
evaluating some prefix expressions: the %3value%* function in {yonss(P2)}.

.TURN ON "#";
A strong point of postfix string notation is
its ease of evaluation.  
First, since we know that
 plus and times are both binary operations, the punctuation,
#],#[, and ;#,# is redundant (this is also true for prefix notation).
Thus the string, 2#3#5#*#+, contains the same information as [2;[3;5]*]+.

Using "↓" to point to the current position in the string
and using the "|#...#|"-notation of {yon(P43)} to represent the stack,
 the following is a trace of the evaluation of the above string, 2#3#5#*#+.

.BEGIN tabit2(19,46); GROUP
.BOXA
↓		        ↓		    ↓
2 3 5 * + ;|   |  =>  3 5 * + ;| 2 |  => 5 * + ;\| 3 |  =>
\\| 2 |
.PT18

↓		 ↓
* + ; | 5 |  =>  + ;\| 15 |  => | 17 | 
      | 3 |\|  2 |
      | 2 |

.BOXB
.END
.FP
It is a very simple  task to program this scheme in LISP,
and  it is quite simple to extend this evaluation scheme to
n-ary operators.

Given an arbitrary arithmetic expression involving constants, and
the binary operations of plus and times, we have a straightforward
mechanical evaluation scheme. It is intuitively clear how to translate
infix expressions into postfix notation.  If we could mechanize this
process then we  would have an algorithm for the evaluation of infix
expressions.  First let's attempt to describe precisely the class
of infix expressions which we  wish to evaluate. The BNF notation
is a good vehicle. Perhaps the following:

.BEGIN TABIT2(20,30) GROUP
.BOXA
\<exp>\::= <exp><binop><exp>
\\::= <integer>
.PT2
\<binop>\::= + | *     
.END
.BOXB
.FP
There are many difficulties with this grammar.  First,
many expressions have more than one possible description or parse tree; the grammar
is said to be %2ambiguous%1. Second, this grammar doesn't express our 
usual precedence relations. The next attempt is successful:

.BEGIN TABIT3(20,31,57) GROUP
.P68:
.BOXA
\<exp>\::= <exp> + <term>\(1)
\\::= <term>\(2)
.PT2
\<term>\::= <term> * <factor>\(3)
\\::= <factor>\(4)
.PT2
\<factor>\::= ( <exp> )\(5)
\\::= <integer>\(6)
.PT2
\<integer>\::= 0 | 1 | 2  . . .\(7)
.BOXB
.END
.FP
.GROUP;
.FP
For example the (only) parsing of 2+3*5 is:
.BEGIN VERBATIM GROUP
.BOXA
.KRK
		   <exp>
		      |
	     <exp>  +  <term>
	      |               |
	   <term>     <term>*<factor>
	      |             |           |
	   <factor>  <factor>  <integer>
	       |            |               |
	   <integer>  <integer>      5
	       |           |
	       2          3


.BOXB
.END
.APART

.BEGIN INDENT 0,10;GROUP
Our next step is based on  the following:
.FP
Assumption: Given an arbitrary, well-formed, arithmetic expression, e,
of our above class, we can find the left-most well-formed 
subexpression, s, such that s is an instance of the RHS of
one of the rules, (1)-(7). Let e%9'%1 be the expression 
obtained from e, by replacing the occurrence of the RHS by the
LHS; then our assumption is also applicable to e%9'%1.
.END

.BEGIN TABS 29,47,73;GROUP;NOFILL;TURN ON "\";
.krk
.BOXA
For example, 
.PT2
e\s\e%9'%*\rule
.PT2
  2+3*5\  2\<integer>+3*5\(7)
<integer>+3*5\<integer>\<factor>+3*5\(6)
<factor>+3*5\<factor>\<term>+3*5\(4)
<term>+3*5\<term>\<exp>+3*5\(2)
<exp>+3*5\3\<exp>+<integer>*5\(7)
<exp>+<integer>*5\<integer>\<exp>+<factor>*5\(6)
<exp>+<factor>*5\<factor>\<exp>+<term>*5\(4)
<exp>+<term>*5\5\<exp>+<term>*<integer>\(7)
<exp>+<term>*<integer>\<integer>\<exp>+<term>*<factor>\(6)
<exp>+<term>*<factor>\<term>*<factor>\<exp>+<term>\(3)
<exp>+<term>\<exp>+<term>\<exp>\(1)
.BOXB
.END
.FP
Now we  associate an action with each of the rules (1)-(7) such
that whenever we apply one of the rules in the above reduction 
technique, we will also execute the corresponding action. We
will also designate an initialization routine which will be
executed at the beginning of the reduction.


.BEGIN GROUP;turn off "←";
.boxa
.FP
Initialization: Let V[0:N] be a vector indexed from 0 to N, where N
is at least as long as the input character string.
Let i be an integer variable, initialized to 0.
.TABIT3(5,16,40) 
.BOXA
.turn on "\";
\\rule\    action
.PT2
\<exp>\::= <exp> + <term>\V(i) ← `+'; i ← i+1
\\::= <term>\ do nothing
.PT2
\<term>\::= <term>*<factor>\V(i) ← `*'; i ← i+1
\\::= <factor>\ do nothing
.PT2
\<factor>\::= (<exp>)\ do nothing
\\::= <integer>\ do nothing
.PT2
\<integer>\::= 0 | 1 | ...\V(i) ← 0 | V(i) ← 1 | ... ; i ← i+1
.BOXB
.END
.GROUP;
.FP
Again performing the reduction of the expression, 2+3*5, but now
executing the action routines as well we find the  contents of V
will contain the following:

.BEGIN VERBATIM GROUP
.KRK
.BOXA
        
	      V: 0 1 2 3 4 
		  2
		  2 3
		  2 3 5
		  2 3 5 *
		  2 3 5 * +

.BOXB
.END
.APART
.FP
That is, the postfix form of the arithmetic expression is formed in V.

So combining the  algorithms for  infix-to-postfix translation, with    postfix
evaluation, we could obtain an infix evaluator. However, we
can do better. By a simple change to the action routines we can
perform infix evaluation as we reduce   the expression.

.FP
.boxa
Initialization: Let V[0:N] be a vector and let i be an integer-valued
variable, initialized to 0.
.BEGIN tabit3(1,12,39); GROUP;TURN OFF "←";
.BOXA
\\ rule\  action
.PT2
\<exp>\::= <exp>+<term>\V(i-2) ← V(i-1)+V(i-2); i ← i-1
\\::= <term>\ do nothing
.PT2
\<term>\::= <term>*<factor>\V(i-2) ← V(i-1)*V(i-2); i ← i-1
\\::= <factor>\ do nothing
.PT2
\<factor>\::= (<exp>)\ do nothing
\\::= <integer>\ do nothing
.PT2
\<integer>\::= 0 | 1 | ...\V(i) ← 0 | V(i) ← 1| ... ; i ← i+1
.BOXA
.END
.FP
When the arithmetic expression has been recognized, V(0) will
contain the value of that expression.
Notice  that the combination of V and its index i, is performing as a
stack in this translator. That is: when we see an integer, we push it into the
stack; when we see a  binary  operator we pop the two operands, perform the
operation and push the result back on the stack.

This technique of associating action routines (also called semantic
routines) with the BNF (or syntax) equations is extremely powerful.
Such processes are called syntax-directed. 

.BOXA
.BEGIN TURN ON "←";
.CENT(Project)
.PT2
.FP
Write a LISP program to perform infix to postfix translation; and then modify
it to perform infix evaluation. Write your programs two ways: first use an
explicit stack; then use recursion to operate with an implicit stack.
.BOXA
.CENT(Project)
.PT2
.FP
As a further example of syntax-directed processes recall the set
of expressions evaluated by ⊗→%3tgmoaf%1↔←: the five primitives under 
composition of functions, all with constant arguments.
Write syntax equations and action routines to effect the evaluation of
such expressions.
.END
.REQUIRE "NOTES.PDQ" SOURCE_FILE;